<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3845：ZCC loves Minecraft</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">ZCC loves Minecraft</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">ZCC loves Minecraft</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                ZCC loves Minecraft                </h1>
                <p>时间限制：3s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：32MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div>ZCC loves playing Minecraft, a sandbox construction game, with his friends. Each friend built his own house, which can be regarded as a point in a plane. However, their houses are so dispersed that they often get attacked by monsters on the way to others' houses. Fortunately, monsters won't come into being in the bright areas. ZCC planned to light a point set S up, through which his friends can visit each other safely. S should include every house. For the convenience of transport, the intersection of S and an arbitrary horizon or vertical line should be empty, a point, or a single continuous segment. This definition is similar to the definition of convex hull, but the line can only be horizon or vertical here because everything in Minecraft is formed by cubes. ZCC also wanted to minimize the area of S to save money.</div>
<div>After working hard for a long time, ZCC obtained the solution. However, as ZCC became more and more famous, the number of his friends increased sharply. Every time a new friend joins the game, ZCC have to calculate S again. He needs your help.</div>
<div>Notice that S may not be continuous, but it's guaranteed that S is continuous at any time. The situation of the following figure will never occur.</div>
<div><img src="../file/3845_0.jpg" width="272" height="210" alt="" /></div>
<p></p></p><hr/><h3>输入格式</h3><p><div>
<div>The input contains several test cases.</div>
<div>Each test case contains n+1 lines.</div>
<div>A integer N(1&le;N&le;100000) will exist in the first line of each input,which represents the number of friends.</div>
<div>The i-th (2&le;i&le;n+1) line contains two integers x,y (-100000&le;x,y&le;100000),which represent the coordinate of the i-1-th friend.</div>
</div>
<p></p></p><hr/><h3>输出格式</h3><p><div>Output should contain n lines.</div>
<div>The i-th line is a number that is the area of S after the i-th friend joins the game.</div>
<p></p></p><hr/><h3>样例输入</h3><pre>5
0 0
0 5
3 3
1 1
2 -1</pre><hr/><h3>样例输出</h3><pre>0
0
0
2
6
</pre><hr/><h3>提示</h3><p><p>The blue areas in the following pictures represent point set S.</p>
<div><img src="../file/3845_0.jpg" width="561" height="233" alt="" /></div>
<p></p></p><hr/><h3>题目来源</h3><p>By 镇海中学</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3845" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3845" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>